package lc20240603;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author 不知名帅哥
 * @version 1.0
 * @description 被围绕的区域，dfs递归解法
 * @date 2024/6/3 17:12
 */
public class AreaSurrounded {
    public static void main(String[] args) {

//        char[][] board={
//                {'X', 'X', 'X', 'X'}, {'X', 'O', 'O', 'X'}, {'X', 'X', 'O', 'X'}, {'X', 'O', 'X', 'X'}
//        };
        char[][] board = {{'O', 'X', 'X', 'O', 'X'}, {'X', 'O', 'O', 'X', 'O'}, {'X', 'O', 'X', 'O', 'X'}, {'O', 'X', 'O', 'O', 'O'}, {'X', 'X', 'O', 'X', 'O'}};
        AreaSurrounded areaSurrounded = new AreaSurrounded();
        areaSurrounded.solve(board);
        for (char[] chars : board) {
            System.out.println(chars);
        }
    }

    public void solve(char[][] board) {
        if (board == null || board.length == 0) {
            return;
        }
        int m = board.length;
        int n = board[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                boolean isEdge = i == 0 || j == 0 || i == m - 1 || j == n - 1;
                //从边缘开始。
                if (isEdge && board[i][j] == 'O') {
//                    dfs(board,i,j);
                    dfs_NonRecursion(board, i, j);
                }
            }
        }

        for (char[] chars : board) {
            System.out.println(chars);
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                }
                if (board[i][j] == '#') {
                    board[i][j] = 'O';
                }
            }
        }
    }


    //深度优先搜索
    private void dfs(char[][] board, int i, int j) {
        if (board == null) {
            return;
        }
        if (i < 0 || j < 0 || i >= board.length || j >= board[0].length || board[i][j] == 'X' || board[i][j] == '#') {
            return;
        }
        board[i][j] = '#';

        dfs(board, i + 1, j);
        dfs(board, i - 1, j);
        dfs(board, i, j + 1);
        dfs(board, i, j - 1);
    }

    class Node {
        int i;
        int j;
        char value;

        public Node(int i, int j, char value) {
            this.i = i;
            this.j = j;
            this.value = value;
        }
    }

    //非递归解法
    private void dfs_NonRecursion(char[][] board, int a, int b) {
        Deque<Node> stack = new ArrayDeque<>();
        //push初始节点
        board[a][b] = '#';
        stack.push(new Node(a, b, board[a][b]));
        int m = board.length;
        int n = board[0].length;
        while (!stack.isEmpty()) {
            Node cur = stack.pop();
            int i = cur.i;
            int j = cur.j;
            //向上
            if (0 < i - 1 && board[i - 1][j] == 'O') {
                stack.push(new Node(i - 1, j, board[i - 1][j]));
                board[i - 1][j] = '#';
            }

            //向下
            if (i + 1 < m && board[i + 1][j] == 'O') {
                stack.push(new Node(i + 1, j, board[i + 1][j]));
                board[i + 1][j] = '#';
            }
            //向左
            if (j - 1 > 0 && board[i][j - 1] == 'O') {
                stack.push(new Node(i, j - 1, board[i][j - 1]));
                board[i][j - 1] = '#';
            }
            //向右
            if (j + 1 < n && board[i][j + 1] == 'O') {
                stack.push(new Node(i, j + 1, board[i][j + 1]));
                board[i][j + 1] = '#';
            }
//            stack.pop();
        }
    }
}
